package com.lw.leetcode.back.c;

import java.util.ArrayList;
import java.util.List;

/**
 * back
 * c
 * 51. N 皇后
 * 面试题 08.12. 八皇后
 * 52. N皇后 II
 *
 * @Author liw
 * @Date 2021/4/15 9:13
 * @Version 1.0
 */
public class SolveNQueens {

    private static int nn = 0;

    public static void main(String[] args) {

        List<List<String>> i = new SolveNQueens().solveNQueens(8);
        System.out.println(i);
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> all = new ArrayList<>();
        if (n == 1) {
            List<String> list = new ArrayList<>();
            list.add("Q");
            all.add(list);
            return all;
        }
        // 采用回溯
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[0] = i;
            totalNQueens(arr, 1, n, all);
        }
        return all;
    }


    public static void totalNQueens(int[] arr, int limit, int n, List<List<String>> all) {
        for (int i = 0; i < n; i++) {
            // 判断是发横竖斜是否有碰撞。
            boolean flag = true;
            for (int k = 0; k < limit; k++) {
                int item = arr[k];
                if (item == i || item - k == i - limit || item + k == i + limit) {
                    flag = false;
                }
            }
            if (flag) {
                arr[limit] = i;
                if (limit != n - 1) {
                    totalNQueens(arr, limit + 1, n, all);
                } else {
                    add(arr, all, n);
                }
            }
        }
    }

    private static void add(int[] arr, List<List<String>> all, int n) {
        List<String> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            int value = arr[i];
            StringBuilder sb = new StringBuilder(n);
            for (int j = 0; j < value; j++) {
                sb.append('.');
            }
            sb.append('Q');
            for (int j = value + 1; j < n; j++) {
                sb.append('.');
            }
            list.add(sb.toString());
        }
        all.add(list);
    }


//    public static List<List<String>> solveNQueens(int n) {
//
//    }

}
